import pandas as pd
import matplotlib.pyplot as plt
sorts = [
"selection",
"bubble",
"bubble-iverson-1",
"bubble-iverson-2",
"insertion",
"bin-insertion",
"counting",
"radix",
"merge",
"quick",
"heap",
"shell-ciura",
"shell"
]
arrays = [
"small-range",
"big-range",
"almost-sorted",
"reversed"
]
data = pd.read_csv('../data/time-small.csv', sep=';', header=None)
data.columns = ['sort', 'array', 'size', 'time']
def print_sort(data, sort):
sort_df = data[data['sort'] == sort]
plt.figure(figsize=(20, 20))
for array in arrays:
df = sort_df[sort_df['array'] == array]
plt.plot(df['size'], df['time'], label=array)
plt.title(sort)
plt.xlabel('Array Size')
plt.xticks(sort_df['size'].unique())
plt.ylabel('Time (nanoseconds)')
plt.legend(labelcolor='black', prop={'size': 15})
def print_array(data, array):
array_df = data[data['array'] == array]
plt.figure(figsize=(20, 20))
for sort in sorts:
df = array_df[array_df['sort'] == sort]
plt.plot(df['size'], df['time'], label=sort)
plt.title(array)
plt.xlabel('Array Size')
plt.xticks(array_df['size'].unique())
plt.ylabel('Time (nanoseconds)')
plt.legend(labelcolor='black', prop={'size': 15})
для размера массива от 100 до 4000, шаг 100
print_sort(data, sorts[0])
Вывод: для массивов небольшого размера сортировка показывает себя примерно одинаково для предложенных типов массива, но всё же на reversed и big range массивах чуть хуже, потому что мы чаще меняем минимальный элемент (предположение)
print_sort(data, sorts[1])
Вывод: видно, что алгоритм чувствителен к порядку элементов, так как от этого зависит количество свопов. Например, худший результат для reversed массива, потому что мы каждый раз свопаем элемент со всеми элементами меньше. Наоборот, alomost sorted быстрее всех отсортировался, так как там минимальное количество свопов
print_sort(data, sorts[2])
Вывод: в дополнение к аргументу из предыдущего пункта стоит отметить значительную оптимизацию для almost sorted благодаря флагу с проверкой Айверсона
print_sort(data, sorts[3])
Вывод: кажется, что существенно дополнить предыдущий пункт нечем: улучшение для almost sorted есть благодаря первому условию
print_sort(data, sorts[4])
Вывод: (даже два)
alomost sorted быстрое исполнение за счёт того, что мы делаем мало вставок с перемещениемsmall range оптимизация за счёт того, что для сдвига условие строгое и мы не трогаем равные элементыprint_sort(data, sorts[5])
Вывод: как мне кажется, бинарный поиск стабилизировал расположение кривых относительно предыдущего пункта. Сама оптимизация поиска места вставки сгладила различие между almost sorted и остальными
print_sort(data, sorts[6])
Вывод: графику совсем плохо( В теории должна быть линия
print_sort(data, sorts[7])
Вывод: Сортировка нечувствительна к порядку элементов, поэтому для всех массивов время сортировки примерно одинаково
print_sort(data, sorts[8])
Вывод: по графику можно сделать вывод, что для merge sort порядок элементов не принципиален
print_sort(data, sorts[9])
Вывод: логично, что для случайного набора сортировка стремится к nlogn, а для отсортированного/почти отсортированного вырождается в квадрат, потому что мы делаем первый элемент опорным и вместо деления на 2 вероятностно равные части получаем "бамбук"
print_sort(data, sorts[10])
Вывод: диапазон значений немного влияет на сортировку, потому что в алгоритме heapify используется строгий знак для обмена значений
print_sort(data, sorts[11])
Вывод: последовательность подобрана для случайных массивов, поэтому они показывают среднее время, но, в частности, хороша для почти отсортированных и плоха для отсортированных в обратном порядке
print_sort(data, sorts[12])
Вывод: диапазон значений негативно влияет на скорость сортировки, потому нам приходит чаще свопать элементы
print_array(data, arrays[0])
Вывод: занятно, что хуже всех пузырёк с условием Айверсона 1+2, возможно, у меня неоптимальный алгоритм. insertion скорее всего выигрывает за счёт константы
print_array(data, arrays[1])
Вывод: видимо, сгенерировался удачный массив для quick, потому что там константа не самая маленькая
print_array(data, arrays[2])
Вывод: тут хорошо видна линейная сложность counting и отчасти radix
print_array(data, arrays[3])
Вывод: здесь можно отметить чувствительные к порядку элементов сортировки